"""Graph.py
Description:
Simple, undirected and connected graph implementation for course 75.29
Teoria de Algoritmos at University of Buenos Aires. Provide simple graph
operations, calculates the minimum spanning tree using Kruskal algorithm
and work with Union and Set dataStructures defined on DisjointSet code,
which represent a Union by rank and uses path compression.

Authors:
Garay, Ignacio
Liguori, Ariel
Musumeci, Pablo
"""
import re
import heapq
from DisjointSets import *

class Edges:
	def __init__(self, vertex1, vertex2, weight):
		self.vertex1 = vertex1
		self.vertex2 = vertex2
		self.weight = weight
	def __str__(self):
		s= "%s -> %s : %s" % (self.vertex1, self.vertex2, self.weight)
		return s
		
class Vertex:
	def __init__(self, value):
		self.value = value

	def __str__(self):
		return self.value

class Graph:
	
	def __str__(self):
		#Imprime el contenido de los vertices y las aristas
		s = "Vertex -> Edges\n"
		for k, v in self.graph.iteritems():
			s+= "%s -> %s\n" % (k, v)
		return s
		
	def __init__(self):
		self.graph = {}
        
	def __init__(self, filePointer):
		#Construye el graph a partir de parsear el archivo
		self.graph = {}
	
		for line in filePointer:
			lines = line.replace(' ','').split(':')
			# Guardo el vertice actual
			verticeActual = lines[0]
			if (not self.isVertex(Vertex(verticeActual))):
				self.addVertex(Vertex(verticeActual))
				
			num = ""
			verticeVecino = ""
			cadena = lines[1]
			# Proceso la linea
			for i in range(len(cadena)):
				char = cadena[i]
				if (char == ')'):
					# Agrego arista entre VActual y V que estoy procesando
					x = int(num)
					#print "Agrego arista %s , %s , %s" % (verticeActual, verticeVecino, x)
					self.addEdge( Edges(Vertex(verticeActual), Vertex(verticeVecino), x) )
					#print "("+verticeActual +","+ verticeVecino+"," +num+")"
				elif (char == '('):
					num = ""
				elif (char == ','):
					verticeVecino = num
					if (not self.isVertex(Vertex(verticeVecino))):
						self.addVertex(Vertex(verticeVecino))
					num = ""
				else:
					num += char
			

	def addVertex(self, vertice):
        #Agrega un vertice al graph
		self.graph[vertice.value] = {}
 
	def delVertex(self, vertice):
        #Si el vertice esta en el graph, lo remueve
		try:
			self.graph.pop(vertice)
			return True
		except KeyError:
            #El vertice no estan en el graph
			return False

	def isVertex(self, vertice):
        #Retorna true si el vertice esta en el geafo
		try:
			self.graph[vertice.value]
			return True
		except KeyError:
			return False
		
	def addEdge(self, edge):
        #Agrega una arista si los vertices existen
		try:
			self.graph[edge.vertex1.value][edge.vertex2.value] = edge.weight
			self.graph[edge.vertex2.value][edge.vertex1.value] = edge.weight
			#print "V1: ",self.graph[edge.vertex1.value]
			#print "V2: ",self.graph[edge.vertex2.value]
			return True
		except KeyError:
			print "Error trying to add edge: Vertexs doesn't belong to graph"
            #Los vertices no estan en el graph
			return False
 
	def delEdge(self, vertice1, vertice2):
        #Remueve la arista del graph
		try:
			self.graph[vertice][vertice2].pop()
			return True
		except KeyError:
            #Los vertices no estan en el graph
			print "Error: Vertexs doesn't belong to graph"
			return False
            
	def getEdge(self, vertice1, vertice2):
		try:
			return self.graph[vertice1][vertice2]
		except KeyError:
			#Los vertices no estan en el grafo
			print "Error: Vertexs doesn't belong to graph"
			return False
		
	# Kruskal Definition
	# - create a forest F (a set of trees), where each vertex in the graph is a separate tree
	# - create a set S containing all the edges in the graph
	# - while S is nonempty and F is not yet spanning
	#	  remove an edge with minimum weight from S
	#	  if that edge connects two different trees, then add it to the forest, combining the trees, 
	# 		otherwise discard that edge.
	# - At the termination of the algorithm, the forest has only one component (ST).
	# Complexity order: O (E log E) + O(V) + O(E)
	#   - Since G is connected |E| >= |V| --> O( E log E) + O(E) + O(E) --> O(E log E)
	#   - |E| <= |V|^2 -> log |E| = O(2 log V) = O(log V)
	#   - Finally the worst case analysis is: O ( E log V)
	def kruskal(self):

		edges = []
		
		# E=Edges; V=Vertex
		# O(|E| log E)
		for u in self.getAllVertex(): #O(1)
			for v in self.getVecinos(u): #O(1)
				heapq.heappush(edges, (self.getEdge(u,v),Edges(u,v,self.getEdge(u,v))) ) #O(1)
	
		T = []  #this contains all the edges in the tree
	
		# O( |V| * MakeSet) = O(V)
		for vertex in self.getAllVertex():
			MakeSet(vertex) #O(1) See dijoint set for verification.
	
		#O(E)
		while edges:
			min_edge = heapq.heappop(edges)[1] #O(E)
			if FindSet(min_edge.vertex1) is not FindSet(min_edge.vertex2): #O(2 log E) = O(log E)
				#perform a union and add this edge to the Tree
				T.append(min_edge) #O(1)
				Union(min_edge.vertex1, min_edge.vertex2) #O(log E)
		return T
	
	def getAllVertex(self):
		# Devuelve una lista con todos los vertices
		return self.graph.keys()	
	
	def getAllEdges(self):
		edges = []
		for u in self.getAllVertex():
			for v in self.getVecinos(u):
				heapq.heappush(edges, Edges(u,v,self.getEdge(u,v)))
		return edges

	def getVecinos(self, vertex):
		try:
			return self.graph[vertex]
		except KeyError:
			print "Error: Vertex doesn't belong to graph"
			return False
    
